Recall: Principle of Mathematical Induction (PMI)

If P(n0)P\left(n_{0}\right) is True (Basis Step)
and P(k)P(k+1)P(k) \rightarrow P(k+1) is True, kn0\forall k \geqslant n_{0} (Inductive Step) then nn0P(n)\forall n \geqslant n_{0}\quad P(n) is a true proposition.

Example Prove 58n3n,n15\mid 8^{n}-3^{n}, \forall n \geqslant 1

Let P(n):58n3nP(n): 5\mid 8^{n}-3^{n}

For n=1,P(1):58131n=1,\quad P(1): 5\mid 8^{1}-3^{1} \checkmark this is true

assume that P(k)P(k) is true ie., 58k3k5\mid 8^{k}-3^{k}
Thus 8k3k=5t8^{k}-3^{k}=5 t \quad for some tZ+t \in \mathbb{Z}^{+}

ie 8k=3k+5t8^{k}=3^{k}+5 t

Now

8k+13k+1=8(8k)3k+1=8(3k+5t)3k+1=83k3k+1+5(8t)=83k33k+5(8t)=(83)3k+5(8t)=53k+5(8t)=5(3k+8tZ+) \begin{aligned} 8^{k+1}-3^{k+1} & =8\left(8^{k}\right)-3^{k+1} \\ & =8\left(3^{k}+5 t\right)-3^{k+1} \\ & =8 \cdot 3^{k}-3^{k+1}+5(8 t) \\ & =8 \cdot 3^{k}-3\cdot 3^{k}+5(8 t) \\ & =(8-3) 3^{k}+5(8 t) \\ & =5 \cdot 3^{k}+5\left( 8 t\right) \\ & =5(\underbrace{3^{k}+8 t}_{\in\Bbb{Z}^+}) \end{aligned}

This divides 5P(k+1)\text{This divides 5} \therefore P(k+1) is true

Thus 58n3nn1,nZ+5\mid 8^{n}-3^{n} \quad \forall n\geqslant 1,\quad n \in \mathbb{Z}^{+}

Note It is not surprizing that 5 divides 8n3n8^{n}-3^{n} since 83=58-3=5 and we have the general result

Thu Let x,yR,nZ+x, y \in \mathbb{R}, n \in \mathbb{Z}^{+}. Then

xnyn=(xy)k=0n1xn1kyk=(xy){xn1+xn2y++xyn2+yn1} \begin{aligned} x^{n}-y^{n} & =(x-y) \sum_{k=0}^{n-1} x^{n-1-k} y^{k} \\ & =(x-y)\left\{x^{n-1}+x^{n-2} y+\cdots+x y^{n-2}+y^{n-1}\right\} \end{aligned}

Proof Let f(n)=k=0n1xn1kyk\displaystyle f(n)=\sum_{k=0}^{n-1} x^{n-1-k} y^{k}

Our result then takes the form

nZ+{xnyn=(xy)f(x)} as  \forall n \in \mathbb{Z}^{+}\left\{x^{n}-y^{n}=(x-y) f(x)\right\} \text { as }

a universally quantified proposition

We prove this result by the principle of mathematical induction:

P(1):xy=(xy)k=00x0kyk=(xy){x0y0}=xy\displaystyle P(1): x-y=(x-y) \sum_{k=0}^{0} x^{0-k} y^{k}=(x-y)\left\{x^{0} y^{0}\right\}=x-y

This is a trivial case. There is nothing proven
As a safety precaution, we check PP(2)P P(2), which is not a trivial case.

P(2):x2y2=(xy)(x+y)P(2): \quad x^{2}-y^{2}=(x-y)(x+y) and

x+y=k=01x1kyk=x1yk+x0y1=x+y x+y=\sum_{k=0}^{1} x^{1-k} y^{k}=x^1 y^{k}+x^{0} y^1=x+y

and P(2)P(2) is true

Assume now that P(k)P(k) is true, where k1k \geqslant 1.

Then

xk+1yk+1=x(xkyk)+xykyk+1=x(xkyk)+(xy)yk=x(xy)f(k)+(xy)yk,by hypothesis=(xy)[xf(k)+yk]=(xy)[xl=0k1xk1lyl+yk]=(xy)[l=0k1xklyl+yk]=(xy)[l=0k1xklyl+x0yk]=(xy)[l=0k1xklyl+xkkyk]=(xy)l=0kxklyl=(xy)f(k+1) \begin{align} x^{k+1}-y^{k+1}&=x\left(x^{k}-y^{k}\right)+x y^{k}-y^{k+1} \\ &=x\left(x^{k}-y^{k}\right)+(x-y) y^{k} \\ &=x(x-y) f(k)+(x-y) y^{k},\text{by hypothesis} \\ &=(x-y)\left[x f(k)+y^{k}\right] \\ &=(x-y)\left[x \sum_{l=0}^{k-1} x^{k-1-l} y^{l}+y^{k}\right] \\ &=(x-y)\left[\sum_{l=0}^{k-1} x^{k-l} y^{l}+y^{k}\right] \\ &=(x-y)\left[\sum_{l=0}^{k-1} x^{k-l} y^{l}+x^{0} y^{k}\right] \\ &=(x-y)\left[\sum_{l=0}^{k-1} x^{k-l} y^{l}+x^{k-k} y^{k}\right] \\ &=(x-y) \sum_{l=0}^{k} x^{k-l} y^{l}=(x-y) f(k+1) \end{align}

Thus P(k)P(k+1)P(k) \rightarrow P(k+1) and by principle of mathematical induction

n1,P(n) \boxed{\forall n \geqslant 1, P(n)}

ie. xnyn=(xy)(xn1+xn2y++xyn2+yn1)x^{n}-y^{n}=(x-y)\left(x^{n-1}+x^{n-2} y+\cdots+x y^{n-2}+y^{n-1}\right)

x3y3=(xy)(x2+xy+y2) x^{3}-y^{3}=(x-y)\left(x^{2}+x y+y^{2}\right)

The buy to principle of mathematical induction is being able to show that P(k)P(k+1)P(k) \rightarrow P(k+1).

If we can only show P(k+1)P(k+1) is two by using more than one previous case,

ie, P(kl+1)P(kl+2)P(k1)P(k)l casesP(k+1)\underbrace{P(k-l+1) \wedge P(k-l+2) \wedge \cdots \wedge P(k-1) \wedge P(k)}_{\textit{l cases}} \rightarrow P(k+1)

can we still prove nP(n)\forall n P(n) is true?

The answer is yes if we expand our basis step to include the first ll propositions

Stronger Principle of Mathematical Induction (SPMI)

If (A) P(1)P(2)P(l)P(1) \wedge P(2) \wedge \cdots \wedge P(l) is TrueTrue me

and (B) P(kl+1)P(k)P(k+1)P(k-l+1) \wedge \cdots \wedge P(k) \rightarrow P(k+1) true, kl\forall k \geqslant l

Then n1P(n)\forall n \geqslant 1 P(n) is true


This form of induction is useful in proving results about recursively defined quantities

Example Let {hn}n=1+\left\{h_{n}\right\}_{n=1}^{+\infty} be a sequence defined by

h1=1,h2=2,h3=3hn=hn1+hn2+hn3,n=4,5, prove hn3(n1)=f(n),n=1,2,3, \begin{aligned} & h_{1}=1, h_{2}=2, h_{3}=3 \\ & h_{n}=h_{n-1}+h_{n-2}+h_{n-3},\quad n=4,5, \cdots \\ & \text { prove } h_{n} \leq 3^{(n-1)}=f(n),\quad \forall n=1,2,3, \cdots \end{aligned}

Solution The recurrence relation says that hnh_{n} depends on 3 previous terms in the sequence, so we use SPMl with l=3l=3\
Let P(x):hn3n1=f(n)P(x): h_{n} \leq 3^{n-1}=f(n)

The basis Step

n=1,h1=1,f(1)=30=1,P(1) is Tn=2,h2=2,f(2)=31=3,P(2) is Tn=3,h3=3,f(3)=32=9,P(3) is T \begin{aligned} & n=1, \quad h_{1}=1,\quad f(1)=3^{0}=1,\quad P(1) \text { is } T \\ & n=2, \quad h_{2}=2,\quad f(2)=3^1=3,\quad P(2) \text { is } T \\ & n=3, \quad h_{3}=3,\quad f(3)=3^{2}=9,\quad P(3) \text { is } T \end{aligned}

Inductive Step

assume P(k2)P(k1)P(k)P(k-2) \wedge P(k-1) \wedge P(k) is True.

Then

hk+1=hk+hk1+hk23k1+3k2+3k3 by hypothesis =3k3(1+3+9)=3k313<3k327=3k=f(k+1) \begin{aligned} h_{k+1} & =h_{k}+h_{k-1}+h_{k-2} \\ & \leq 3^{k-1}+3^{k-2}+3^{k-3} \quad \text { by hypothesis } \\ & =3^{k-3}(1+3+9)\\ & =3^{k-3}\cdot 13\lt 3^{k-3} \cdot 27=3^{k}=f(k+1) \end{aligned}

P(k+1)\therefore P(k+1) is True and n1,hn3n1 \forall n \geqslant 1,\quad h_{n} \leq 3^{n-1} \text {. }

Exercise p35055,14,5,7,18,19p 350 \rightarrow 55,1 \geqslant 4,5,7,18,19

Why Does PMI WORK?
Well Ordered Principle
Every non-empty subset of Z\mathbb{Z} that is bounded below has a lead element

A set is bounded below if kZ\exists k \in \mathbb{Z} such that k<x,xk<x,\quad \forall x in the set.

Suppose P(1)P(1) is true
and P(k)P(k+1),k1P(k) \rightarrow P(k+1),\quad \forall k \geqslant 1.

Let us suppose, if possible, that there is one integer greater than 00 such that P(n)P(n) is false.

Let S={xZ+P(x)S=\left\{x \in \mathbb{Z}^{+} \mid P(x)\right. is False }\} \neq \emptyset

By Well Ordered Principle S1S^1 has a least element n0n_{0} and since P(1)P(1) is true, n0>1n_{0}>1 and P(n0)P\left(n_{0}\right) is false

Thus n01Z+n_{0}-1 \in \mathbb{Z}^{+}and n01<n0n_{0}-1<n_{0} so n01Sn_{0}-1 \notin S and P(n01)P\left(n_{0}-1\right) is true.

But P(n01)P(n0)P\left(n_{0}-1\right) \rightarrow P\left(n_{0}\right) so P(n0)P\left(n_{0}\right) is TT, contradicting statement

Thus our assumption that SS \neq \emptyset leads to a contradiction. Thus S=S=\emptyset and hence P(n)P(n) is tue, x1\underbar{}\forall x \geqslant 1


The Well Ordered Principle has other applications. Consider the following example

Example a proof that 2\sqrt{2} is irrational

Suppose 2=ab,a,bZ+\sqrt{2}=\frac{a}{b},\qquad a, b \in \mathbb{Z}^{+}

Let S={xZ+x=k2S=\left\{x \in \mathbb{Z}^{+} \mid x=k \sqrt{2}\right., for some kZ+}\left.k \in \mathbb{Z}^{+}\right\}.

SS \neq \emptyset since a=b2Sa=b \sqrt{2} \in S by assumption

By W.0.P. SS has a least element tt and tZ+,t=s2t \in \mathbb{Z}^{+}, \quad t=s \sqrt{2} for some particular sZ+s \in \mathbb{Z}^{+}

Consider now the number x=t2tx=t \sqrt{2}-t. We have x=t2t=t2Δ2=(tΔ)2x=t \sqrt{2}-t=t \sqrt{2}-\Delta \sqrt{2}=(t-\Delta) \sqrt{2}\
Now xZx \in \mathbb{Z} since t2=s2Z+t \sqrt{2}=s \cdot 2 \in \mathbb{Z}^{+}

Also x=t2t=t(21)>0x=t \sqrt{2}-t=t(\sqrt{2}-1)>0 since 2>1\sqrt{2}>1, so xZ+x \in \mathbb{Z}^{+}

Thus xSx \in S. Also x=t2t=t(21)<tx=t \sqrt{2}-t=t(\sqrt{2}-1)<t since 2<2\sqrt{2}<2

Then tt is not the least element of SS.

Thus S=S=\emptyset, and 2R\sqrt{2} \notin \mathbb{R}


Note It can be shown that

PMI is equivalent to the W.D.P. in the following sense.

We showed WOPPMIWOP \Rightarrow P M I by assuming WOP as an axiom of the integers
An axiom is something that we assume to be true, or a basic law from which we deduce properties of a structure

If we take P.M.I as an axiom, then it is possible to show

 PMI  W.O.P.  \text { PMI } \Rightarrow \text { W.O.P. }

Cardinality of Sets

Recall that in lecture 7, we briefly considered the cardinality of set
We defined the cardinality of a finite set to be S=|S|= the number of elements in S=nS=n where xZ,x0x \in \mathbb{Z}, x \geqslant 0.

We include 00 as a cardinality, the cardinality of the empty set =0\mid \emptyset\mid =0

We also asserted, that if S=n<+|S|=n<+\infty then the number of subsets of SS is 2x2^{x} ie, P(s)=2n=2S|P(s)|=2^{n}=2^{\left| S \right| }.

We constructed the outline of a proof of this fact using the principle of Mathematical induction

We will shortly give a direct proof of P(s)=2n|P(s)|=2^{n}\
Fist we consider cardinality of seta in a formal way

Recall

a function f:ABf: A \rightarrow B is called 111-1 when f(x)=f(y)x=yf(x)=f(y) \leftrightarrow x=y

a function is called onto if bB,aA\forall b \in B, \exists a \in A such that f(a)=bf(a)=b.

a function that is 111-1 and onto is called a bijection between AA and BB

Definition the sets AA and BB have the same cardinality if and only if a\exists a bijection between AA and BB.

From this most general definition we see that the cardinality of a finite set is the number of elements in the set. arbitrarily label the elements, one, two,... up to nn and we get a bijection from {1,2,,n}\{1,2, \cdots, n\} to the set in question.

If a set cannot be put into a 111-1 correspondence with {1,,n}\{1, \ldots, n\} for any xx, we say the set is infinite

Now there is more than one cardinality for an infinite set

If a set AA is not finite and there is a bijection between AA and Z+={1,2,,n,}\mathbb{Z}^{+}=\{1,2, \cdots, n, \cdots\} we say AA is countably infinite

A countably infinite set is also called denumerable

If a set AA is finite oR countably infinite we say AA is countable

Theorem I

The following conditions are equivalent

  1. A is countable
  2. \exists onto map from Z+\mathbb{Z}^{+}to AA.
  3.  11\exists\ 1-1 map from AA to Z+\mathbb{Z}^{+}

Proof A is countable means AA is finite or AA is in a 111-1 correspondence with Z+\mathbb{Z}^{+}

If there exists an onto map from Z+\mathbb{Z}^{+} then AA is either finite or countably infinite
If there exists a 111-1 map from AA into Z+\mathbb{Z}^{+} then AA is either finite on countably infinite

This theorem is really a restatement of the definitions of the terms involved

If AA is an infinite set, it need not be countable. If AA is infinite and not countable, ie \exists no 111-1 bijection of AA with Z+\mathbb{Z}^{+}, we say AA is uncountable

Examples

  1. Z+{0}\mathbb{Z}^{+} \cup\{0\} is countable.

For nX+n \in \mathbb{X}^{+}, define f(n)=n1f(n)=n-1.

Then f:Z+Z+{0}f: \mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+} \cup\{0\} is 111-1 and onto

  1. Z={kkZ+}\mathbb{Z}^{-}=\left\{-k \mid k \in \mathbb{Z}^{+}\right\}is countable. Let f:Y+Zf: \mathbb{Y}^{+} \rightarrow \mathbb{Z}^{-}be defined by f(x)=xf(x)=-x. ff is bijection.
  2. Z\mathbb{Z} is countable.

To prove this last assertion we first prove the following

Theorem 2

Theorem 2 The union of two countable sets is countable.

Proof Let AA and BB be countable sets

There are 3 cases to consider

  1. A, B both finite
  2. one of AA and BB is infinite
  3. A,BA, B both infinite

Case (1). We have already seen that of

A=n,B=m then AB=A+BAB<+ \begin{aligned} &|A|=n,|B|=m \text { then } \\ &|A \cup B|=|A|+|B|-|A \cap B|<+\infty \end{aligned}

So ABA\cup B is finite and thus countable.

Case 2) Suppose, without loss of generality that A=n<+|A|=n<+\infty and BB is countably infinite

Let f:Z+Bf: \mathbb{Z}^{+} \rightarrow B be a bijection

Suppose we have listed the elements of AA as a finite sequence.

A={a1,,an}={g(1),,g(n)} A=\left\{a_{1}, \cdots, a_{n}\right\} = \{g(1), \ldots, g(n)\}

where gg is a bijection from {1,.,x}\{1, ., x\} to AA.

Define h:Z+ABh: \mathbb{Z}^{+} \rightarrow A \cup B \quad by

h(k)={g(k),1knf(kn),n+1k h(k)= \begin{cases}g(k), & 1 \leq k \leq n \\ f(k-n), & n+1 \leq k\end{cases}

Then h:Z+ABh: \mathbb{Z}^{+} \rightarrow A \cup B is an onto map

We cant guarantee that it is 111-1, since ABA \cap B may be non-empty, but onto suffices to show ABA\cup B is countably infinite and hence countable by Theorem 1

Case 3 A+BA+B infinite.

LetA={f(t),,f(n)}B={g(1),,g(n),} \begin{align} Let\quad A&=\{f(t), \ldots, f(n)\}\\ B&=\{g(1), \cdots, g(n), \ldots\} \end{align}

where f,gf, g are bijections of Z+\mathbb{Z}^{+}to AA and BB, respectively

Define h(k)={f(l),k=2l,l=1,2,g(l),k=2l1,l=1,2,h(k)= \begin{cases}&f(l), &k=2 l-, l=1,2, \ldots \\ &g(l), &k=2 l-1, l=1,2, \ldots\end{cases}

hh is an onto map of Z+\mathbb{Z}^{+}with ABA \cup B
Hence ABA \cup B is countable

Z\mathbb{Z} is countable, since Z=(Z+{0})Z\mathbb{Z}=\left(\mathbb{Z}^{+} \cup\{0\}\right) \cup \mathbb{Z}^{-}

When a set is countably infinite we define ito cardinality to be 0\alef_0 (aleph zeno, aleph naught) and we write

Z=Z+=0 |\mathbb{Z}|=| \mathbb{Z}^{+} \mid=\alef_{0}

Lemma Any subset of a countable set is countable

Proof: If f:Z+Af: \Bbb{Z}^{+} \rightarrow A is onto, then BAB \subseteq A adopt ff by sending f1(AB)f^{-1}(A-B) to any element of BB, then the new ff is an onto map of Z+\mathbb{Z}^{+}onto BB, use Theorem 1

There are infinite sets that are not countable
The power set of Z\mathbb{Z}^{\top} is uncountable

Before we prove this assertion, lat us consider the power sets of finite sets and how to "count" the number of their elements

Bit strings

a bit is a single digit, either 00 or 11
A bit string of length nn is a string of nn fits, 0 owl, strung together

Example: 1011011011000010110110110000 is a bit string of length 14

Fact There are 2n2^{n} bit strings of length nn

Proof There are 2 choices for the first bit, 00 or 11 . For each choice, there are 2 choices for the second bit, on 222^{2} in total. For the 3nd bit we have 2 chries fore each of the 222^{2} choices for the first two bit, ie 232^{3} choices fore the first 3 bits, and so on: (and so on is short hand for "proof by induction")

Let A={a1,a2,,an}A=\left\{a_{1}, a_{2}, \cdots, a_{n}\right\} be a finite set For BAB \subseteq A, let xBx_{B} be the bit string of length a where

 the kth  bit of xB={1 if akB0 if akB \text { the } k^{\text {th }} \text { bit of } x_{B}=\left\{\begin{array}{lll} 1 & \text { if } & a_{k} \in B \\ 0 & \text { if } & a_{k} \notin B \end{array}\right.

For example, xB=000nx_{B}=00 \cdots 0_{n} represents the empty set A\emptyset \subseteq A and
xB=111nx_{B}=11 \cdots 1_{n} represents AAA \subseteq A.

Let BP(A)B \in P(A). Define f(B)=xBf(B)=x_{B}.

Then f:P(A)f: P(A) \rightarrow Bit n={_{n}=\{ bit-strings of length n}n\}

ff is a bijection

It is 111-1 because because if two bit-strings are different, they came from different subsets and it is onto since every bit sting corresponds to a subset of AA.

Thus P(A)=Bitn=2n|P(A)|=\mid Bit_n \mid=2^{n} when A=n<+|A|=n<+\infty

Now turn our attention to countable infinite sets

Each subset of A now is represented by a bit string of infinite length.

xA=1111x=0000 \begin{aligned} & x_{A}=1111 \cdots \\ & x_{\emptyset}=0000 \cdots \end{aligned}

and the map f:P(A)Bitf: P(A) \rightarrow Bit_\infty defined by the same process as before is 111-1 and onto

We show bit \infty is not countable by contradiction

Suppose that Bit=0\mid Bit_\infty \mid=\alef_{0}.

Then it is possible to list all the elements of Bit
Suppose Bit={x1,x2,,}Bit_\infty=\left\{x_{1}, x_{2}, \cdots,\right\} where we
write

x1=x11x12x13x1nx2=x21,x22x23x2nxn=xn1xn=xn3 xnn \begin{aligned} & x_{1}=x_{11} x_{12} x_{13}\quad &\cdots\quad x_{1 n} \cdots \\ & x_{2}=x_{21}, x_{22} x_{23}\quad &\cdots\quad x_{2 n} \cdots \\ &\vdots \\ & x_{n}=x_{n 1} x_{n=} x_{n 3}\quad &\cdots\ x_{n-n} \cdots \\ &\vdots \\ \end{aligned}

Where xij=0x_{i j}=0 or 11

Define xBitx^{*} \in Bit_\infty by

x=x1x2x3xn x^{*}=\quad x_{* 1}\quad x_{* 2}\quad x_{* 3}\quad \cdots\quad x_{* n}\quad \cdots

where xn={0 if xnn=11 if xnn=0x_{* n}= \begin{cases}0 & \text { if } x_{n n}=1 \\ 1 & \text { if } x_{n n}=0\end{cases}

Then xxk,k=1,2,x^{*} \neq x_{k}, \forall k=1,2, \ldots

Thus xx^{*} is not on the list. Thus every list is incomplete. Thus there is nn list of all

the element of BitBit_\infty, so BitBit_\infty\infty is uncountable

We define Bit=P(Z+)=201\mid Bit_\infty|=| P\left(\mathbb{Z}^{+}\right) \mid=2^{\alef_{0}} \equiv \alef_{1}

Is there a set of numbers that we can say has the same cardinality as P(Z+)P\left(\Bbb{Z}^{+}\right)?

The rational numbers Q\Bbb{Q} won't work since they are countable. This is a consequence of the following result.

Theorem A countable union of countable sets is countable.

Proof Let the sets be listed

A1,A2,,An2, A_{1}, A_{2}, \cdots, A_{n_{2}}, \cdots

and their elements listed

Ak={ak1,ak2,,akn,} A_{k}=\left\{a_{k 1}, a_{k 2}, \cdots, a_{k n}, \cdots\right\}

Now list the elements of k=1Ak\displaystyle\bigcup_{k=1}^{\infty} A_{k} as shown below

a11,ai2,a13,a14,a21,a22,a23,a24,a31,a32,a33,a34,a41,,a42,a43,a44, \begin{aligned} & a_{11}^{\prime}, a_{i 2}^{\prime}, a_{13}^{\prime}, a_{14}^{\prime}, \cdots \\ & a_{21}^{\prime}, a_{22}^{\prime}, a_{23}^{\prime}, a_{24}, \cdots \\ & a_{31}^{\prime}, a_{32}^{\prime}, a_{33}, a_{34}, \cdots \\ & a_{41}, \cdots, a_{42}^{\prime}, a_{43}, a_{44}, \end{aligned}

If we write k=1Ak={a1,a2,a3,}\displaystyle\bigcup_{k=1}^{\infty} A_{k}=\left\{a_{1}, a_{2}, a_{3}, \ldots\right\}

then a1=a11,a2=a12,a3=a21a_{1}=a_{11}, a_{2}=a_{12}, a_{3}=a_{21}, etc.

This scheme generates f:Z+f: \mathbb{Z}^{+}onto k=1Ak\displaystyle\bigcup_{k=1}^{\infty} A_{k}. and k=1Ak\displaystyle\bigcup_{k=1}^{\infty} A_{k} is countable.

Hilbert Hotel

Now the rational numbers Q\Bbb{Q} is the countable union of the sets Q[k,k+1]\Bbb{Q}[k, k+1] where

Q[k,k+1]={xQkxk+1,kZ} \Bbb{Q}[k, k+1]=\{x \in \Bbb{Q} \mid k \leq x \leq k+1, k \in \mathbb{Z}\}

We now prove Q[0,1]\Bbb{Q}[0,1] is countable.

Let xQ[0,1]x \in \Bbb{Q}[0,1], then x=pq,q,pZ+,qp\displaystyle x=\frac{p}{q},\quad q, p \in \mathbb{Z}^{+},\quad q \geqslant p

Let An={nk,kZ+,kn}A_{n}=\left\{\frac{n}{k},\quad k \in\Bbb{Z}^{+},\quad k \geqslant n\right\} \quad for nZ+n \in \mathbb{Z}^{+}

AnA_{n} is countably infinite.

Q[0,1]={0}(n=1An)\displaystyle\Bbb{Q}[0,1]=\{0\} \cup\left(\bigcup_{n=1}^{\infty} A_{n}\right) is the countable union of countable seta.

Thus Q\mathbb{Q} is countable


The real numbers, R\mathbb{R}, are uncountable and R=P(Z+)=1|\mathbb{R}|=\left|P\left(\mathbb{Z}^{+}\right)\right|=\alef_{1} sometimes CC for continuum

We show this by showing R=Bit|\mathbb{R}|=\mid Bit_\infty \mid
First we will show that [0,1]=Bit|[0,1]|=\mid Bit_\infty\mid and then we show [0,1]=R|[0,1]|=|\mathbb{R}|.


When we considered changing bases in L13L_{13} we mainly considered different bases for integers We have only used "decimal expansions" for real and rational numbers

The change of base theorem can be modified to show that every decimal expansion can be convected to a "binary expansion"

Every real number can be written in the form ka=k+a,kZk\cdot a=k+a,\quad k \in \mathbb{Z} and aBita \in Bit_\infty.

Thus, for k=0,[0,1]=k=0,|[0,1]|=\mid Bit =1_{\infty} \mid=\alef_{1}
also note (0,1)=[0,1]|(0,1)|=|[0,1]|

To show that R=[0,1]|\mathbb{R}|=|[0,1]| we can use a number of techniques to find a 111-1, onto map between (0,1)(0,1) and R\mathbb{R}

There are a number of analytic methods using functions known to us ( or maybe not known )

Ex f(x)=cot(πx)f(x)=\cot (\pi x) is a 111-1 onto map form (0,1)(0,1) to R\mathbb{R}.

A geometric method in to wrap the interval (0,1)(0,1) into a circle and use stereographic projection.

This provides a 111-1 onto map of (0,1)(0,1) with R\mathbb{R}.

Cardinalities of infinite sets is a very rich topic (and hard) which we will leave for later courses

For further details read §2.5\S 2.5 of the text, to get an idea of the history of these results

Theorem Let AA be uncountable and BB be countable, BAB \subseteq A

then A\BA \backslash B is uncountable.

Proof Assume A\BA \backslash B is countable
Then A=(A\B)BA=(A \backslash B) \cup B is the union of two countable sets and hence countable
Therefore AA is countable, a contradiction

A\B\therefore A \backslash B is uncountable.